home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2460 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.3 KB
  1. Path: newshost.lanl.gov!tanmoy
  2. From: tanmoy@qcd.lanl.gov (Tanmoy Bhattacharya)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: quick decision: is n a power of 2?
  5. Date: 21 Jan 1996 17:44:04 GMT
  6. Organization: Los Alamos National Laboratory
  7. Message-ID: <TANMOY.96Jan21104404@qcd.lanl.gov>
  8. References: <Pine.OSF.3.91.960119114608.18779E-100000@io.UWinnipeg.ca>
  9.     <4dpian$gij@oxy.rust.net> <9601201820.AA01752@dxmint.cern.ch>
  10. NNTP-Posting-Host: qcd.lanl.gov
  11. Mime-Version: 1.0
  12. Content-Type: text
  13. In-reply-to: Dan Pop's message of Sat, 20 Jan 1996 19:20:47 +0100
  14.  
  15. --text follows this line--
  16. In article <9601201820.AA01752@dxmint.cern.ch> Dan Pop
  17. <danpop@mail.cern.ch> writes: 
  18. <snip>
  19.    >Given some number, there is a neat trick to generate a mask which will
  20.    >have exactly one bit set in it.  The bit set will be the least
  21.    >significant non-zero bit in the original number:
  22.    >
  23.    >    mask = ~number & number;
  24.    >
  25.    >Now, if number contained a single non-zero bit (and is therefore a
  26.    >power of 2),  mask will be equal to number.  Therefore:
  27.    >
  28.    >   if (number == (~number & number))
  29.    >   {
  30.    >        /* number is a power of 2 */
  31.    >   }
  32.    >
  33.    >Try it, you'll like it!
  34.  
  35.    I don't think so.  ~number & number will _always_ give 0.  -number & number
  36.    will actually work, except for the case when number == 0.  That is,
  37.    assuming a two's complement implementation.  On a one's complement or
  38.    sign-magnitude implementation it won't work at all.
  39.  
  40. Consider x = 0...0101. -x = 1...1011
  41. -x & x == 1. So I cannot quite figure out what was meant above.
  42.  
  43. x && !(x & ~-x) is a possible solution: But since ~-x is the same as
  44. (x-1), this is the same as an already posted answer. (I am sorry that
  45. in my hurry I missed the x && bit in a previous post).
  46.  
  47. Instead of calling for 2's complement arithmetic, I prefer to say that
  48. these should only be used for unsigned types. 
  49.  
  50. Cheers
  51. Tanmoy
  52. --
  53. tanmoy@qcd.lanl.gov(128.165.23.46) DECNET: BETA::"tanmoy@lanl.gov"(1.218=1242)
  54. Tanmoy Bhattacharya O:T-8(MS B285)LANL,NM87545 H:#9,3000,Trinity Drive,NM87544
  55. Others see <gopher://yaleinfo.yale.edu:7700/00/Internet-People/internet-mail>,
  56. <http://alpha.acast.nova.edu/cgi-bin/inmgq.pl>or<ftp://csd4.csd.uwm.edu/pub/
  57. internetwork-mail-guide>. -- <http://nqcd.lanl.gov/people/tanmoy/tanmoy.html>
  58. fax: 1 (505) 665 3003   voice: 1 (505) 665 4733    [ Home: 1 (505) 662 5596 ]
  59.